package jvzhen;

import java.util.*;

public class JvZhen {
    /*给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

     */
    public static void setZeroes(int[][] matrix) {
        boolean[] row = new boolean[matrix.length];
        boolean[] col = new boolean[matrix[0].length];
        for(int i = 0;i< matrix.length;i++){
            for(int j = 0;j<matrix[0].length;j++){
                if(matrix[i][j] == 0){
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        for(int i = 0;i< matrix.length;i++){
            for(int j = 0;j<matrix[0].length;j++){
                if(row[i] ||col[j]){
                    matrix[i][j] = 0;
                }
            }
        }
    }
    /*
    给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
     */

    public static List<Integer> spiralOrder(int[][] matrix) {
       List <Integer> res = new ArrayList<>();
       int top = 0;
       int left = 0;
       int right = matrix[0].length-1;
       int bottom = matrix.length-1;
       int sum = matrix.length * matrix[0].length;
       int index = 1;
       while(index<=sum){
           for(int i = left;i<=right&&index<=sum;i++){
               res.add(matrix[top][i]);
               index++;
           }
           top++;
           for(int i = top;i<=bottom&&index<=sum;i++){
               res.add(matrix[i][right]);
               index++;
           }
           right--;
           for(int i = right;i>=left&&index<=sum;i--){
               res.add(matrix[bottom][i]);
               index++;
           }
           bottom--;
           for(int i = bottom;i>=top&&index<=sum;i--){
               res.add(matrix[i][left]);
               index++;
           }
           left++;
       }
       return res;
    }
/*
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
 */
public static void rotate(int[][] matrix) {
  //求出转置矩阵
    int index = 0;
    for(int i = 0;i<=index&&index<matrix.length;i++){
        for(int j = i;j< matrix[0].length;j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
        index++;
    }
    //将矩阵的每一行都逆序

    for(int i = 0;i<matrix.length;i++){
        int right = matrix[0].length-1;
        int left = 0;
        while(left<right){
            int temp = matrix[i][right];
            matrix[i][right] = matrix[i][left];
            matrix[i][left] = temp;
            right--;
            left++;
        }
    }
}
/*
给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。
示例 1：
输入：mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
输出：true
解释：顺时针轮转 90 度一次可以使 mat 和 target 一致。
示例 2：
输入：mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
输出：false
解释：无法通过轮转矩阵中的元素使 equal 与 target 一致。
示例 3：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
输出：true
解释：顺时针轮转 90 度两次可以使 mat 和 target 一致。
 */
public static  boolean findRotation(int[][] mat, int[][] target) {
        for(int i = 0;i<4;i++){
            rotate(mat);
            if(Arrays.deepEquals(mat,target)){
                return true;
            }
        }
        return false;
}
/*
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
 */
    public static boolean searchMatrix(int[][] matrix, int target) {
                int left = 0;
                int right = matrix[0].length-1;
                boolean b = false;
                for(int i = 0;i< matrix.length;i++){
                    if(matrix[i][0]>target){
                        continue;
                    }
                    b = binarySrarch(matrix[i], target, left, right);
                    if(b == true){
                        break;
                    }
                }
                return b;
    }
    public static  boolean binarySrarch(int [] arr,int target,int left ,int right){
            int mid = (left+right)/2;
            int midVal = arr[mid];
            if(left>right){
                return false;
            }
            if(midVal<target){
               return binarySrarch(arr,target,mid+1,right);
            }else if(midVal>target){
                return binarySrarch(arr,target,left,mid-1);
            }else{
                return true;
            }
    }
    /*
    z字型查找
     */
    public static boolean searchMatrix1(int[][] matrix, int target) {
       
       return false;
    }

}
